﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol114
{


    public void Flatten2(TreeNode root)//直接把左子树放到右边，然后把右边接到左子树的最右边
    {
        while (root != null)
        {
            if (root.left != null)
            {

                TreeNode pre = root.left;

                while (pre.right != null)
                {
                    pre = pre.right;
                }

                pre.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
            else
            {
                //直接去右边
                root = root.right;
            }

        }
    }
    TreeNode pre=null;
    public void Flatten3(TreeNode root)//递归法，反向先序遍历，根左右变为右左根，其实是后序左右根，先右
    {


        if (root == null)
        {
            return;
        }

        //右
        Flatten(root.right);
        Flatten(root.left);

        //访问根
        root.right=pre;
        root.left=null;
        pre = root;//更新一下


    
    }

    public void FlattenPostOrder(TreeNode root)//迭代法，反向先序遍历，根左右变为右左根，其实是后序左右根，先右
    {
        //这个方法实现了右左根的遍历，但是改变了root的位置

        TreeNode pre=root;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (root != null||stack.Count>0) {

            while (root != null) { 
            
            
            
            stack.Push(root);
                root = root.right;

            
            }
            root = stack.Pop();
            if (root.left != null&& root.left != pre) {

                stack.Push(root);//重新入栈(两种情况，有有孩子并且右孩子没有遍历过
                root = root.left;
            }
            else
            {

                Console.WriteLine(root.val);

                //root.right = pre;
                //root.left = null;

                pre = root;
                //root = root.right;//root要从栈里面出来，而不是右边
                root = null;
            }
       



        
        }


    
    
    }
    public void Flatten(TreeNode root)//迭代法，反向先序遍历，根左右变为右左根，其实是后序左右根，先右
    {
        //这个方法实现了右左根的遍历，但是改变了root的位置

        TreeNode pre = null;
        TreeNode cur = root;

        Stack<TreeNode> stack = new Stack<TreeNode>();

        while (cur != null || stack.Count > 0)
        {

            while (cur != null)
            {



                stack.Push(cur);
                cur = cur.right;


            }
            cur = stack.Pop();
            if (cur.left != null && cur.left != pre)
            {

                stack.Push(cur);//重新入栈(两种情况，有有孩子并且右孩子没有遍历过
                cur = cur.left;
            }
            else
            {

                Console.WriteLine(cur.val);

                cur.right = pre;
                cur.left = null;

                pre = cur;
                //root = root.right;//root要从栈里面出来，而不是右边
                cur = null;
            }





        }




    }
}


class Program114
{
    static void Main114()
    {
        string s = "1 2 3 4 5 6";
        string[] chars = s.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 3, 2, 4, 1, 5, 6 };

        Solution105 solution105 = new Solution105();



        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);


        Sol114 sol = new Sol114();
        sol.Flatten(root);
        TreeNode res = root;
        while (res != null)
        {
            Console.WriteLine(res.val);
            res = res.right;

        }

    }
}

